home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 14 / CU Amiga Magazine's Super CD-ROM 14 (1997)(EMAP Images)(GB)(Track 1 of 3)[!][issue 1997-09].iso / CUCD / Programming / Mesa-2.2 / src-glu / nurbsutl.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-27  |  23.1 KB  |  962 lines
  1. /* $Id: nurbsutl.c,v 1.1 1996/09/27 01:19:39 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  2.0
  6.  * Copyright (C) 1995-1996  Brian Paul
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25.  * $Log: nurbsutl.c,v $
  26.  * Revision 1.1  1996/09/27 01:19:39  brianp
  27.  * Initial revision
  28.  *
  29.  */
  30.  
  31.  
  32. /*
  33.  * NURBS implementation written by Bogdan Sikorski (bogdan@cira.it)
  34.  * See README2 for more info.
  35.  */
  36.  
  37.  
  38. #include <math.h>
  39. #include "nurbs.h"
  40.  
  41. GLenum
  42. test_knot(GLint nknots, GLfloat *knot, GLint order)
  43. {
  44.     GLsizei i;
  45.     GLint knot_mult;
  46.     GLfloat tmp_knot;
  47.  
  48.     tmp_knot=knot[0];
  49.     knot_mult=1;
  50.     for(i=1;i<nknots;i++)
  51.     {
  52.         if(knot[i] < tmp_knot)
  53.             return GLU_NURBS_ERROR4;
  54.         if(fabs(tmp_knot-knot[i]) > EPSILON)
  55.         {
  56.             if(knot_mult>order)
  57.                 return GLU_NURBS_ERROR5;
  58.             knot_mult=1;
  59.             tmp_knot=knot[i];
  60.         }
  61.         else
  62.             ++knot_mult;
  63.     }
  64.     return GLU_NO_ERROR;
  65. }
  66.  
  67. /* qsort function */
  68. static int
  69. knot_sort(const void *a, const void *b)
  70. {
  71.     GLfloat x,y;
  72.  
  73.     x=*((GLfloat *)a);
  74.     y=*((GLfloat *)b);
  75.     if(fabs(x-y) < EPSILON)
  76.         return 0;
  77.     if(x > y)
  78.         return 1;
  79.     return -1;
  80. }
  81.  
  82. /* insert into dest knot all values within the valid range from src knot */
  83. /* that do not appear in dest */
  84. void
  85. collect_unified_knot(knot_str_type *dest, knot_str_type *src,
  86.     GLfloat maximal_min_knot, GLfloat minimal_max_knot)
  87. {
  88.     GLfloat *src_knot,*dest_knot;
  89.     GLint src_t_min,src_t_max,dest_t_min,dest_t_max;
  90.     GLint src_nknots,dest_nknots;
  91.     GLint i,j,k,new_cnt;
  92.     GLboolean    not_found_flag;
  93.  
  94.     src_knot=src->unified_knot;
  95.     dest_knot=dest->unified_knot;
  96.     src_t_min=src->t_min;
  97.     src_t_max=src->t_max;
  98.     dest_t_min=dest->t_min;
  99.     dest_t_max=dest->t_max;
  100.     src_nknots=src->unified_nknots;
  101.     dest_nknots=dest->unified_nknots;
  102.  
  103.     k=new_cnt=dest_nknots;
  104.     for(i=src_t_min;i<=src_t_max;i++)
  105.         if(src_knot[i] - maximal_min_knot > -EPSILON &&
  106.         src_knot[i] - minimal_max_knot < EPSILON)
  107.     {
  108.         not_found_flag=GL_TRUE;
  109.         for(j=dest_t_min;j<=dest_t_max;j++)
  110.             if(fabs(dest_knot[j]-src_knot[i]) < EPSILON)
  111.             {
  112.                 not_found_flag=GL_FALSE;
  113.                 break;
  114.             }
  115.         if(not_found_flag)
  116.         {
  117.             /* knot from src is not in dest - add this knot to dest */
  118.             dest_knot[k++]=src_knot[i];
  119.             ++new_cnt;
  120.             ++(dest->t_max); /* the valid range widens */
  121.             ++(dest->delta_nknots); /* increment the extra knot value counter */
  122.         }
  123.     }
  124.     dest->unified_nknots=new_cnt;
  125.     qsort((void *)dest_knot,(size_t)new_cnt,(size_t)sizeof(GLfloat),
  126.         &knot_sort);
  127. }
  128.  
  129. /* basing on the new common knot range for all attributes set */
  130. /* t_min and t_max values for each knot - they will be used later on */
  131. /* by explode_knot() and calc_new_ctrl_pts */
  132. static void
  133. set_new_t_min_t_max(knot_str_type *geom_knot, knot_str_type *color_knot,
  134.     knot_str_type *normal_knot, knot_str_type *texture_knot,
  135.     GLfloat maximal_min_knot, GLfloat minimal_max_knot)
  136. {
  137.     GLuint    t_min,t_max,cnt;
  138.  
  139.     if(minimal_max_knot-maximal_min_knot < EPSILON)
  140.     {
  141.         /* knot common range empty */
  142.         geom_knot->t_min=geom_knot->t_max=0;
  143.         color_knot->t_min=color_knot->t_max=0;
  144.         normal_knot->t_min=normal_knot->t_max=0;
  145.         texture_knot->t_min=texture_knot->t_max=0;
  146.     }
  147.     else
  148.     {
  149.         if(geom_knot->unified_knot!=NULL)
  150.         {
  151.             cnt=geom_knot->unified_nknots;
  152.             for(t_min=0;t_min<cnt;t_min++)
  153.                 if(fabs((geom_knot->unified_knot)[t_min] - maximal_min_knot) <
  154.                         EPSILON)
  155.                     break;
  156.             for(t_max=cnt-1;t_max;t_max--)
  157.                 if(fabs((geom_knot->unified_knot)[t_max] - minimal_max_knot) < 
  158.                         EPSILON)
  159.                     break;
  160.         }
  161.         else
  162.         if(geom_knot->nknots)
  163.         {
  164.             cnt=geom_knot->nknots;
  165.             for(t_min=0;t_min<cnt;t_min++)
  166.                 if(fabs((geom_knot->knot)[t_min] - maximal_min_knot) < EPSILON)
  167.                     break;
  168.             for(t_max=cnt-1;t_max;t_max--)
  169.                 if(fabs((geom_knot->knot)[t_max] - minimal_max_knot) < EPSILON)
  170.                     break;
  171.         }
  172.         geom_knot->t_min=t_min;
  173.         geom_knot->t_max=t_max;
  174.         if(color_knot->unified_knot!=NULL)
  175.         {
  176.             cnt=color_knot->unified_nknots;
  177.             for(t_min=0;t_min<cnt;t_min++)
  178.                 if(fabs((color_knot->unified_knot)[t_min] - maximal_min_knot) <
  179.                         EPSILON)
  180.                     break;
  181.             for(t_max=cnt-1;t_max;t_max--)
  182.                 if(fabs((color_knot->unified_knot)[t_max] - minimal_max_knot) < 
  183.                         EPSILON)
  184.                     break;
  185.             color_knot->t_min=t_min;
  186.             color_knot->t_max=t_max;
  187.         }
  188.         if(normal_knot->unified_knot!=NULL)
  189.         {
  190.             cnt=normal_knot->unified_nknots;
  191.             for(t_min=0;t_min<cnt;t_min++)
  192.                 if(fabs((normal_knot->unified_knot)[t_min] - maximal_min_knot) <
  193.                         EPSILON)
  194.                     break;
  195.             for(t_max=cnt-1;t_max;t_max--)
  196.                 if(fabs((normal_knot->unified_knot)[t_max] - minimal_max_knot) < 
  197.                         EPSILON)
  198.                     break;
  199.             normal_knot->t_min=t_min;
  200.             normal_knot->t_max=t_max;
  201.         }
  202.         if(texture_knot->unified_knot!=NULL)
  203.         {
  204.             cnt=texture_knot->unified_nknots;
  205.             for(t_min=0;t_min<cnt;t_min++)
  206.                 if(fabs((texture_knot->unified_knot)[t_min] - maximal_min_knot) 
  207.                         < EPSILON)
  208.                     break;
  209.             for(t_max=cnt-1;t_max;t_max--)
  210.                 if(fabs((texture_knot->unified_knot)[t_max] - minimal_max_knot) 
  211.                         < EPSILON)
  212.                     break;
  213.             texture_knot->t_min=t_min;
  214.             texture_knot->t_max=t_max;
  215.         }
  216.     }
  217. }
  218.  
  219. /* modify all knot valid ranges in such a way that all have the same */
  220. /* range, common to all knots */
  221. /* do this by knot insertion */
  222. GLenum
  223. select_knot_working_range(GLUnurbsObj *nobj,knot_str_type *geom_knot,
  224.     knot_str_type *color_knot, knot_str_type *normal_knot,
  225.     knot_str_type *texture_knot)
  226. {
  227.     GLint max_nknots;
  228.     GLfloat maximal_min_knot,minimal_max_knot;
  229.     GLint i;
  230.  
  231.     /* find the maximum modified knot length */
  232.     max_nknots=geom_knot->nknots;
  233.     if(color_knot->unified_knot)
  234.         max_nknots+=color_knot->nknots;
  235.     if(normal_knot->unified_knot)
  236.         max_nknots+=normal_knot->nknots;
  237.     if(texture_knot->unified_knot)
  238.         max_nknots+=texture_knot->nknots;
  239.     maximal_min_knot=(geom_knot->knot)[geom_knot->t_min];
  240.     minimal_max_knot=(geom_knot->knot)[geom_knot->t_max];
  241.     /* any attirb data ? */
  242.     if(max_nknots!=geom_knot->nknots)
  243.     {
  244.         /* allocate space for the unified knots */
  245.         if((geom_knot->unified_knot=
  246.                 (GLfloat *)malloc(sizeof(GLfloat)*max_nknots))==NULL)
  247.         {
  248.             call_user_error(nobj,GLU_OUT_OF_MEMORY);
  249.             return GLU_ERROR;
  250.         }
  251.         /* copy the original knot to the unified one */
  252.         geom_knot->unified_nknots=geom_knot->nknots;
  253.         for(i=0;i<geom_knot->nknots;i++)
  254.             (geom_knot->unified_knot)[i]=(geom_knot->knot)[i];
  255.         if(color_knot->unified_knot)
  256.         {
  257.             if((color_knot->knot)[color_knot->t_min] - maximal_min_knot >
  258.                     EPSILON)
  259.                 maximal_min_knot=(color_knot->knot)[color_knot->t_min];
  260.             if(minimal_max_knot - (color_knot->knot)[color_knot->t_max] >
  261.                     EPSILON)
  262.                 minimal_max_knot=(color_knot->knot)[color_knot->t_max];
  263.             if((color_knot->unified_knot=
  264.                     (GLfloat *)malloc(sizeof(GLfloat)*max_nknots))==NULL)
  265.             {
  266.                 free(geom_knot->unified_knot);
  267.                 call_user_error(nobj,GLU_OUT_OF_MEMORY);
  268.                 return GLU_ERROR;
  269.             }
  270.             /* copy the original knot to the unified one */
  271.             color_knot->unified_nknots=color_knot->nknots;
  272.             for(i=0;i<color_knot->nknots;i++)
  273.                 (color_knot->unified_knot)[i]=(color_knot->knot)[i];
  274.         }
  275.         if(normal_knot->unified_knot)
  276.         {
  277.             if((normal_knot->knot)[normal_knot->t_min] - maximal_min_knot >
  278.                     EPSILON)
  279.                 maximal_min_knot=(normal_knot->knot)[normal_knot->t_min];
  280.             if(minimal_max_knot - (normal_knot->knot)[normal_knot->t_max] >
  281.                     EPSILON)
  282.                 minimal_max_knot=(normal_knot->knot)[normal_knot->t_max];
  283.             if((normal_knot->unified_knot=
  284.                     (GLfloat *)malloc(sizeof(GLfloat)*max_nknots))==NULL)
  285.             {
  286.                 free(geom_knot->unified_knot);
  287.                 free(color_knot->unified_knot);
  288.                 call_user_error(nobj,GLU_OUT_OF_MEMORY);
  289.                 return GLU_ERROR;
  290.             }
  291.             /* copy the original knot to the unified one */
  292.             normal_knot->unified_nknots=normal_knot->nknots;
  293.             for(i=0;i<normal_knot->nknots;i++)
  294.                 (normal_knot->unified_knot)[i]=(normal_knot->knot)[i];
  295.         }
  296.         if(texture_knot->unified_knot)
  297.         {
  298.             if((texture_knot->knot)[texture_knot->t_min] - maximal_min_knot >
  299.                     EPSILON)
  300.                 maximal_min_knot=(texture_knot->knot)[texture_knot->t_min];
  301.             if(minimal_max_knot - (texture_knot->knot)[texture_knot->t_max] >
  302.                     EPSILON)
  303.                 minimal_max_knot=(texture_knot->knot)[texture_knot->t_max];
  304.             if((texture_knot->unified_knot=
  305.                     (GLfloat *)malloc(sizeof(GLfloat)*max_nknots))==NULL)
  306.             {
  307.                 free(geom_knot->unified_knot);
  308.                 free(color_knot->unified_knot);
  309.                 free(normal_knot->unified_knot);
  310.                 call_user_error(nobj,GLU_OUT_OF_MEMORY);
  311.                 return GLU_ERROR;
  312.             }
  313.             /* copy the original knot to the unified one */
  314.             texture_knot->unified_nknots=texture_knot->nknots;
  315.             for(i=0;i<texture_knot->nknots;i++)
  316.                 (texture_knot->unified_knot)[i]=(texture_knot->knot)[i];
  317.         }
  318.         /* work on the geometry knot with all additional knot values */
  319.         /* appearing in attirbutive knots */
  320.         if(minimal_max_knot-maximal_min_knot < EPSILON)
  321.         {
  322.             /* empty working range */
  323.             geom_knot->unified_nknots=0;
  324.             color_knot->unified_nknots=0;
  325.             normal_knot->unified_nknots=0;
  326.             texture_knot->unified_nknots=0;
  327.         }
  328.         else
  329.         {
  330.             if(color_knot->unified_knot)
  331.                 collect_unified_knot(geom_knot,color_knot,maximal_min_knot,
  332.                     minimal_max_knot);
  333.             if(normal_knot->unified_knot)
  334.                 collect_unified_knot(geom_knot,normal_knot,maximal_min_knot,
  335.                     minimal_max_knot);
  336.             if(texture_knot->unified_knot)
  337.                 collect_unified_knot(geom_knot,texture_knot,maximal_min_knot,
  338.                     minimal_max_knot);
  339.             /* since we have now built the "unified" geometry knot */
  340.             /* add same knot values to all attributive knots */
  341.             if(color_knot->unified_knot)
  342.                 collect_unified_knot(color_knot,geom_knot,maximal_min_knot,
  343.                     minimal_max_knot);
  344.             if(normal_knot->unified_knot)
  345.                 collect_unified_knot(normal_knot,geom_knot,maximal_min_knot,
  346.                     minimal_max_knot);
  347.             if(texture_knot->unified_knot)
  348.                 collect_unified_knot(texture_knot,geom_knot,maximal_min_knot,
  349.                     minimal_max_knot);
  350.         }
  351.     }
  352.     set_new_t_min_t_max(geom_knot,color_knot,normal_knot,texture_knot,
  353.         maximal_min_knot,minimal_max_knot);
  354.     return GLU_NO_ERROR;
  355. }
  356.  
  357. void
  358. free_unified_knots(knot_str_type *geom_knot, knot_str_type *color_knot,
  359.     knot_str_type *normal_knot, knot_str_type *texture_knot)
  360. {
  361.     if(geom_knot->unified_knot)
  362.         free(geom_knot->unified_knot);
  363.     if(color_knot->unified_knot)
  364.         free(color_knot->unified_knot);
  365.     if(normal_knot->unified_knot)
  366.         free(normal_knot->unified_knot);
  367.     if(texture_knot->unified_knot)
  368.         free(texture_knot->unified_knot);
  369. }
  370.  
  371. GLenum
  372. explode_knot(knot_str_type *the_knot)
  373. {
  374.     GLfloat *knot,*new_knot;
  375.     GLint nknots,n_new_knots=0;
  376.     GLint t_min,t_max;
  377.     GLint ord;
  378.     GLsizei i,j,k;
  379.     GLfloat tmp_float;
  380.  
  381.     if(the_knot->unified_knot)
  382.     {
  383.         knot=the_knot->unified_knot;
  384.         nknots=the_knot->unified_nknots;
  385.     }
  386.     else
  387.     {
  388.         knot=the_knot->knot;
  389.         nknots=the_knot->nknots;
  390.     }
  391.     ord=the_knot->order;
  392.     t_min=the_knot->t_min;
  393.     t_max=the_knot->t_max;
  394.  
  395.     for(i=t_min;i<=t_max;)
  396.     {
  397.         tmp_float=knot[i];
  398.         for(j=0;j<ord && (i+j)<=t_max;j++)
  399.             if(fabs(tmp_float-knot[i+j])>EPSILON)
  400.                 break;
  401.         n_new_knots+=ord-j;
  402.         i+=j;
  403.     }
  404.     /* alloc space for new_knot */
  405.     if((new_knot=(GLfloat *)malloc(sizeof(GLfloat)*(nknots+n_new_knots)))==NULL)
  406.     {
  407.         return GLU_OUT_OF_MEMORY;
  408.     }
  409.     /* fill in new knot */
  410.     for(j=0;j<t_min;j++)
  411.         new_knot[j]=knot[j];
  412.     for(i=j;i<=t_max;i++)
  413.     {
  414.         tmp_float=knot[i];
  415.         for(k=0;k<ord;k++)
  416.         {
  417.             new_knot[j++]=knot[i];
  418.             if(tmp_float==knot[i+1])
  419.                 i++;
  420.         }
  421.     }
  422.     for(i=t_max+1;i<(int)nknots;i++)
  423.         new_knot[j++]=knot[i];
  424.     /* fill in the knot structure */
  425.     the_knot->new_knot=new_knot;
  426.     the_knot->delta_nknots+=n_new_knots;
  427.     the_knot->t_max+=n_new_knots;
  428.     return GLU_NO_ERROR;
  429. }
  430.  
  431. GLenum
  432. calc_alphas(knot_str_type *the_knot)
  433. {
  434.     GLfloat tmp_float;
  435.     int i,j,k,m,n;
  436.     int order;
  437.     GLfloat *alpha,*alpha_new,*tmp_alpha;
  438.     GLfloat denom;
  439.     GLfloat *knot,*new_knot;
  440.  
  441.  
  442.     knot=the_knot->knot;
  443.     order=the_knot->order;
  444.     new_knot=the_knot->new_knot;
  445.     n=the_knot->nknots-the_knot->order;
  446.     m=n+the_knot->delta_nknots;
  447.     if((alpha=(GLfloat *)malloc(sizeof(GLfloat)*n*m))==NULL)
  448.     {
  449.         return GLU_OUT_OF_MEMORY;
  450.     }
  451.     if((alpha_new=(GLfloat *)malloc(sizeof(GLfloat)*n*m))==NULL)
  452.     {
  453.         free(alpha);
  454.         return GLU_OUT_OF_MEMORY;
  455.     }
  456.     for(j=0;j<m;j++)
  457.     {
  458.         for(i=0;i<n;i++)
  459.         {
  460.             if((knot[i] <= new_knot[j]) && (new_knot[j] < knot[i+1]))
  461.                 tmp_float=1.0;
  462.             else
  463.                 tmp_float=0.0;
  464.             alpha[i+j*n]=tmp_float;
  465.         }
  466.     }
  467.     for(k=1;k<order;k++)
  468.     {
  469.         for(j=0;j<m;j++)
  470.             for(i=0;i<n;i++)
  471.             {
  472.                 denom=knot[i+k]-knot[i];
  473.                 if(fabs(denom)<EPSILON)
  474.                     tmp_float=0.0;
  475.                 else
  476.                     tmp_float=(new_knot[j+k]-knot[i])/denom*
  477.                         alpha[i+j*n];
  478.                 denom=knot[i+k+1]-knot[i+1];
  479.                 if(fabs(denom)>EPSILON)
  480.                     tmp_float+=(knot[i+k+1]-new_knot[j+k])/denom*
  481.                         alpha[(i+1)+j*n];
  482.                 alpha_new[i+j*n]=tmp_float;
  483.             }
  484.         tmp_alpha=alpha_new;
  485.         alpha_new=alpha;
  486.         alpha=tmp_alpha;
  487.     }
  488.     the_knot->alpha=alpha;
  489.     free(alpha_new);
  490.     return GLU_NO_ERROR;
  491. }
  492.  
  493. GLenum
  494. calc_new_ctrl_pts(GLfloat *ctrl,GLint stride,knot_str_type *the_knot,
  495.     GLint dim,GLfloat **new_ctrl,GLint *ncontrol)
  496. {
  497.     GLsizei i,j,k,l,m,n;
  498.     GLsizei index1,index2;
  499.     GLfloat *alpha;
  500.     GLfloat *new_knot;
  501.  
  502.     new_knot=the_knot->new_knot;
  503.     n=the_knot->nknots-the_knot->order;
  504.     alpha=the_knot->alpha;
  505.  
  506.     m=the_knot->t_max+1-the_knot->t_min-the_knot->order;
  507.     k=the_knot->t_min;
  508.     /* allocate space for new control points */
  509.     if((*new_ctrl=(GLfloat *)malloc(sizeof(GLfloat)*dim*m))==NULL)
  510.     {
  511.         return GLU_OUT_OF_MEMORY;
  512.     }
  513.     for(j=0;j<m;j++)
  514.     {
  515.         for(l=0;l<dim;l++)
  516.             (*new_ctrl)[j*dim+l]=0.0;
  517.         for(i=0;i<n;i++)
  518.         {
  519.             index1=i+(j+k)*n;
  520.             index2=i*stride;
  521.             for(l=0;l<dim;l++)
  522.                 (*new_ctrl)[j*dim+l]+=alpha[index1]*ctrl[index2+l];
  523.         }
  524.     }
  525.     *ncontrol=(GLint)m;
  526.     return GLU_NO_ERROR;
  527. }
  528.  
  529. static GLint
  530. calc_factor(GLfloat *pts,GLint order,GLint indx,GLint stride,GLfloat tolerance,
  531.     GLint dim)
  532. {
  533.     GLdouble model[16],proj[16];
  534.     GLint viewport[4];
  535.     GLdouble x,y,z,w,winx1,winy1,winz,winx2,winy2;
  536.     GLint i;
  537.     GLdouble len,dx,dy;
  538.  
  539.     glGetDoublev(GL_MODELVIEW_MATRIX,model);
  540.     glGetDoublev(GL_PROJECTION_MATRIX,proj);
  541.     glGetIntegerv(GL_VIEWPORT,viewport);
  542.     if(dim==4)
  543.     {
  544.         w=(GLdouble)pts[indx+3];
  545.         x=(GLdouble)pts[indx]/w;
  546.         y=(GLdouble)pts[indx+1]/w;
  547.         z=(GLdouble)pts[indx+2]/w;
  548.         gluProject(x,y,z,model,proj,viewport,&winx1,&winy1,&winz);
  549.         len=0.0;
  550.         for(i=1;i<order;i++)
  551.         {
  552.             w=(GLdouble)pts[indx+i*stride+3];
  553.             x=(GLdouble)pts[indx+i*stride]/w;
  554.             y=(GLdouble)pts[indx+i*stride+1]/w;
  555.             z=(GLdouble)pts[indx+i*stride+2]/w;
  556.             if(gluProject(x,y,z,model,proj,viewport,&winx2,&winy2,&winz))
  557.             {
  558.                 dx=winx2-winx1;
  559.                 dy=winy2-winy1;
  560.                 len+=sqrt(dx*dx+dy*dy);
  561.             }
  562.             winx1=winx2; winy1=winy2;
  563.         }
  564.     }
  565.     else
  566.     {
  567.         x=(GLdouble)pts[indx];
  568.         y=(GLdouble)pts[indx+1];
  569.         if(dim==2)
  570.             z=0.0;
  571.         else
  572.             z=(GLdouble)pts[indx+2];
  573.         gluProject(x,y,z,model,proj,viewport,&winx1,&winy1,&winz);
  574.         len=0.0;
  575.         for(i=1;i<order;i++)
  576.         {
  577.             x=(GLdouble)pts[indx+i*stride];
  578.             y=(GLdouble)pts[indx+i*stride+1];
  579.             if(dim==2)
  580.                 z=0.0;
  581.             else
  582.                 z=(GLdouble)pts[indx+i*stride+2];
  583.             if(gluProject(x,y,z,model,proj,viewport,&winx2,&winy2,&winz))
  584.             {
  585.                 dx=winx2-winx1;
  586.                 dy=winy2-winy1;
  587.                 len+=sqrt(dx*dx+dy*dy);
  588.             }
  589.             winx1=winx2; winy1=winy2;
  590.         }
  591.     }
  592.     len /= tolerance;
  593.     return ((GLint)len+1);
  594. }
  595.  
  596. static GLenum
  597. calc_sampling_3D(new_ctrl_type *new_ctrl, GLfloat tolerance, GLint dim,
  598.     GLint uorder, GLint vorder, GLint **ufactors, GLint **vfactors)
  599. {
  600.     GLfloat        *ctrl;
  601.     GLint        tmp_factor1,tmp_factor2;
  602.     GLint        ufactor_cnt,vfactor_cnt;
  603.     GLint        offset1,offset2,offset3;
  604.     GLint        i,j;
  605.  
  606.     ufactor_cnt=new_ctrl->s_bezier_cnt;
  607.     vfactor_cnt=new_ctrl->t_bezier_cnt;
  608.     if((*ufactors=(GLint *)malloc(sizeof(GLint)*ufactor_cnt*3))
  609.             ==NULL)
  610.     {
  611.         return GLU_OUT_OF_MEMORY;
  612.     }
  613.     if((*vfactors=(GLint *)malloc(sizeof(GLint)*vfactor_cnt*3))
  614.             ==NULL)
  615.     {
  616.         free(ufactors);
  617.         return GLU_OUT_OF_MEMORY;
  618.     }
  619.     ctrl=new_ctrl->geom_ctrl;
  620.     offset1=new_ctrl->geom_t_stride*vorder;
  621.     offset2=new_ctrl->geom_s_stride*uorder;
  622.     for(j=0;j<vfactor_cnt;j++)
  623.     {
  624.         *(*vfactors+j*3+1)=tmp_factor1=calc_factor(ctrl,vorder,
  625.             j*offset1,dim,tolerance,dim);
  626.         /* loop ufactor_cnt-1 times */
  627.         for(i=1;i<ufactor_cnt;i++)
  628.         {
  629.             tmp_factor2=calc_factor(ctrl,vorder,
  630.                 j*offset1+i*offset2,dim,tolerance,dim);
  631.             if(tmp_factor2>tmp_factor1)
  632.                 tmp_factor1=tmp_factor2;
  633.         }
  634.         /* last time for the opposite edge */
  635.         *(*vfactors+j*3+2)=tmp_factor2=calc_factor(ctrl,vorder,
  636.             j*offset1+i*offset2-new_ctrl->geom_s_stride,
  637.             dim,tolerance,dim);
  638.         if(tmp_factor2>tmp_factor1)
  639.             *(*vfactors+j*3)=tmp_factor2;
  640.         else
  641.             *(*vfactors+j*3)=tmp_factor1;
  642.     }
  643.     offset3=new_ctrl->geom_s_stride;
  644.     offset2=new_ctrl->geom_s_stride*uorder;
  645.     for(j=0;j<ufactor_cnt;j++)
  646.     {
  647.         *(*ufactors+j*3+1)=tmp_factor1=calc_factor(ctrl,uorder,
  648.             j*offset2,offset3,tolerance,dim);
  649.         /* loop vfactor_cnt-1 times */
  650.         for(i=1;i<vfactor_cnt;i++)
  651.         {
  652.             tmp_factor2=calc_factor(ctrl,uorder,
  653.                 j*offset2+i*offset1,offset3,tolerance,dim);
  654.             if(tmp_factor2>tmp_factor1)
  655.                 tmp_factor1=tmp_factor2;
  656.         }
  657.         /* last time for the opposite edge */
  658.         *(*ufactors+j*3+2)=tmp_factor2=calc_factor(ctrl,uorder,
  659.             j*offset2+i*offset1-new_ctrl->geom_t_stride,
  660.             offset3,tolerance,dim);
  661.         if(tmp_factor2>tmp_factor1)
  662.             *(*ufactors+j*3)=tmp_factor2;
  663.         else
  664.             *(*ufactors+j*3)=tmp_factor1;
  665.     }
  666.     return GL_NO_ERROR;
  667. }
  668.  
  669. static GLenum
  670. calc_sampling_2D(GLfloat *ctrl, GLint cnt, GLint order,
  671.     GLfloat tolerance, GLint dim, GLint **factors)
  672. {
  673.     GLint        factor_cnt;
  674.     GLint        tmp_factor;
  675.     GLint        offset;
  676.     GLint        i;
  677.  
  678.     factor_cnt=cnt/order;
  679.     if((*factors=(GLint *)malloc(sizeof(GLint)*factor_cnt))==NULL)
  680.     {
  681.         return GLU_OUT_OF_MEMORY;
  682.     }
  683.     offset=order*dim;
  684.     for(i=0;i<factor_cnt;i++)
  685.     {
  686.         tmp_factor=calc_factor(ctrl,order,i*offset,dim,tolerance,dim);
  687.         if(tmp_factor == 0)
  688.             (*factors)[i]=1;
  689.         else
  690.             (*factors)[i]=tmp_factor;
  691.     }
  692.     return GL_NO_ERROR;
  693. }
  694.  
  695. static void
  696. set_sampling_and_culling( GLUnurbsObj *nobj )
  697. {
  698.     if(nobj->auto_load_matrix==GL_FALSE)
  699.     {
  700.         GLint i;
  701.         GLfloat m[4];
  702.  
  703.         glPushAttrib( (GLbitfield) (GL_VIEWPORT_BIT | GL_TRANSFORM_BIT));
  704.         for(i=0;i<4;i++)
  705.             m[i]=nobj->sampling_matrices.viewport[i];
  706.         glViewport(m[0],m[1],m[2],m[3]);
  707.         glMatrixMode(GL_PROJECTION);
  708.         glPushMatrix();
  709.         glLoadMatrixf(nobj->sampling_matrices.proj);
  710.         glMatrixMode(GL_MODELVIEW);
  711.         glPushMatrix();
  712.         glLoadMatrixf(nobj->sampling_matrices.model);
  713.     }
  714. }
  715.  
  716. static void
  717. revert_sampling_and_culling( GLUnurbsObj *nobj )
  718. {
  719.     if(nobj->auto_load_matrix==GL_FALSE)
  720.     {
  721.         glMatrixMode(GL_MODELVIEW);
  722.         glPopMatrix();
  723.         glMatrixMode(GL_PROJECTION);
  724.         glPopMatrix();
  725.         glPopAttrib();
  726.     }
  727. }
  728.  
  729. GLenum
  730. glu_do_sampling_3D( GLUnurbsObj *nobj, new_ctrl_type *new_ctrl,
  731.     GLint **sfactors, GLint **tfactors)
  732. {
  733.     GLint    dim;
  734.     GLenum    err;
  735.  
  736.     *sfactors=NULL;
  737.     *tfactors=NULL;
  738.     dim=nobj->surface.geom.dim;
  739.     set_sampling_and_culling(nobj);
  740.     if((err=calc_sampling_3D(new_ctrl,nobj->sampling_tolerance,dim,
  741.         nobj->surface.geom.sorder,nobj->surface.geom.torder,
  742.         sfactors,tfactors))==GLU_ERROR)
  743.     {
  744.         revert_sampling_and_culling(nobj);
  745.         call_user_error(nobj,err);
  746.         return GLU_ERROR;
  747.     }
  748.     revert_sampling_and_culling(nobj);
  749.     return GLU_NO_ERROR;
  750. }
  751.  
  752. GLenum
  753. glu_do_sampling_2D( GLUnurbsObj *nobj, GLfloat *ctrl, GLint cnt, GLint order,
  754.     GLint dim, GLint **factors)
  755. {
  756.     GLenum err;
  757.  
  758.     *factors=NULL;
  759.     set_sampling_and_culling(nobj);
  760.     if((err=calc_sampling_2D(ctrl,cnt,order,nobj->sampling_tolerance,dim,
  761.         factors))==GLU_ERROR)
  762.     {
  763.         revert_sampling_and_culling(nobj);
  764.         call_user_error(nobj,err);
  765.         return GLU_ERROR;
  766.     }
  767.     revert_sampling_and_culling(nobj);
  768.     return GLU_NO_ERROR;
  769. }
  770.  
  771. /* TODO - i don't like this culling - this one just tests if at least one */
  772. /* ctrl point lies within the viewport . Also the point_in_viewport() */
  773. /* should be included in the fnctions for efficiency reasons */
  774.  
  775. static GLboolean
  776. point_in_viewport(GLfloat *pt, GLint dim)
  777. {
  778.     GLdouble model[16],proj[16];
  779.     GLint viewport[4];
  780.     GLdouble x,y,z,w,winx,winy,winz;
  781.  
  782.     glGetDoublev(GL_MODELVIEW_MATRIX,model);
  783.     glGetDoublev(GL_PROJECTION_MATRIX,proj);
  784.     glGetIntegerv(GL_VIEWPORT,viewport);
  785.     if(dim==3)
  786.     {
  787.         x=(GLdouble)pt[0];
  788.         y=(GLdouble)pt[1];
  789.         z=(GLdouble)pt[2];
  790.         gluProject(x,y,z,model,proj,viewport,&winx,&winy,&winz);
  791.     }
  792.     else
  793.     {
  794.         w=(GLdouble)pt[3];
  795.         x=(GLdouble)pt[0]/w;
  796.         y=(GLdouble)pt[1]/w;
  797.         z=(GLdouble)pt[2]/w;
  798.         gluProject(x,y,z,model,proj,viewport,&winx,&winy,&winz);
  799.     }
  800.     if((GLint)winx >= viewport[0] && (GLint)winx < viewport[2] &&
  801.             (GLint)winy >= viewport[1] && (GLint)winy < viewport[3])
  802.         return GL_TRUE;
  803.     return GL_FALSE;
  804. }
  805.  
  806. GLboolean
  807. fine_culling_test_3D(GLUnurbsObj *nobj,GLfloat *pts,GLint s_cnt,GLint t_cnt,
  808.     GLint s_stride,GLint t_stride, GLint dim)
  809. {
  810.     GLint     i,j;
  811.  
  812.     if(nobj->culling==GL_FALSE)
  813.         return GL_FALSE;
  814.     set_sampling_and_culling(nobj);
  815.     
  816.     if(dim==3)
  817.     {
  818.         for(i=0;i<s_cnt;i++)
  819.             for(j=0;j<t_cnt;j++)
  820.                 if(point_in_viewport(pts+i*s_stride+j*t_stride,dim))
  821.                 {
  822.                     revert_sampling_and_culling(nobj);
  823.                     return GL_FALSE;
  824.                 }
  825.     }
  826.     else
  827.     {
  828.         for(i=0;i<s_cnt;i++)
  829.             for(j=0;j<t_cnt;j++)
  830.                 if(point_in_viewport(pts+i*s_stride+j*t_stride,dim))
  831.                 {
  832.                     revert_sampling_and_culling(nobj);
  833.                     return GL_FALSE;
  834.                 }
  835.     }
  836.     revert_sampling_and_culling(nobj);
  837.     return GL_TRUE;
  838. }
  839.  
  840. /*GLboolean
  841. fine_culling_test_3D(GLUnurbsObj *nobj,GLfloat *pts,GLint s_cnt,GLint t_cnt,
  842.     GLint s_stride,GLint t_stride, GLint dim)
  843. {
  844.     GLint        visible_cnt;
  845.     GLfloat        feedback_buffer[5];
  846.     GLsizei        buffer_size;
  847.     GLint         i,j;
  848.  
  849.     if(nobj->culling==GL_FALSE)
  850.         return GL_FALSE;
  851.     buffer_size=5;
  852.     set_sampling_and_culling(nobj);
  853.     
  854.     glFeedbackBuffer(buffer_size,GL_2D,feedback_buffer);
  855.     glRenderMode(GL_FEEDBACK);
  856.     if(dim==3)
  857.     {
  858.         for(i=0;i<s_cnt;i++)
  859.         {
  860.             glBegin(GL_LINE_LOOP);
  861.             for(j=0;j<t_cnt;j++)
  862.                 glVertex3fv(pts+i*s_stride+j*t_stride);
  863.             glEnd();
  864.         }
  865.         for(j=0;j<t_cnt;j++)
  866.         {
  867.             glBegin(GL_LINE_LOOP);
  868.             for(i=0;i<s_cnt;i++)
  869.                 glVertex3fv(pts+i*s_stride+j*t_stride);
  870.             glEnd();
  871.         }
  872.     }
  873.     else
  874.     {
  875.         for(i=0;i<s_cnt;i++)
  876.         {
  877.             glBegin(GL_LINE_LOOP);
  878.             for(j=0;j<t_cnt;j++)
  879.                 glVertex4fv(pts+i*s_stride+j*t_stride);
  880.             glEnd();
  881.         }
  882.         for(j=0;j<t_cnt;j++)
  883.         {
  884.             glBegin(GL_LINE_LOOP);
  885.             for(i=0;i<s_cnt;i++)
  886.                 glVertex4fv(pts+i*s_stride+j*t_stride);
  887.             glEnd();
  888.         }
  889.     }
  890.     visible_cnt=glRenderMode(GL_RENDER);
  891.  
  892.     revert_sampling_and_culling(nobj);
  893.     return (GLboolean)(visible_cnt==0);
  894. }*/
  895.  
  896. GLboolean
  897. fine_culling_test_2D(GLUnurbsObj *nobj,GLfloat *pts,GLint cnt,
  898.     GLint stride, GLint dim)
  899. {
  900.     GLint     i;
  901.  
  902.     if(nobj->culling==GL_FALSE)
  903.         return GL_FALSE;
  904.     set_sampling_and_culling(nobj);
  905.     
  906.     if(dim==3)
  907.     {
  908.         for(i=0;i<cnt;i++)
  909.             if(point_in_viewport(pts+i*stride,dim))
  910.             {
  911.                 revert_sampling_and_culling(nobj);
  912.                 return GL_FALSE;
  913.             }
  914.     }
  915.     else
  916.     {
  917.         for(i=0;i<cnt;i++)
  918.             if(point_in_viewport(pts+i*stride,dim))
  919.             {
  920.                 revert_sampling_and_culling(nobj);
  921.                 return GL_FALSE;
  922.             }
  923.     }
  924.     revert_sampling_and_culling(nobj);
  925.     return GL_TRUE;
  926. }
  927.  
  928. /*GLboolean
  929. fine_culling_test_2D(GLUnurbsObj *nobj,GLfloat *pts,GLint cnt,
  930.     GLint stride, GLint dim)
  931. {
  932.     GLint        visible_cnt;
  933.     GLfloat        feedback_buffer[5];
  934.     GLsizei        buffer_size;
  935.     GLint         i;
  936.  
  937.     if(nobj->culling==GL_FALSE)
  938.         return GL_FALSE;
  939.     buffer_size=5;
  940.     set_sampling_and_culling(nobj);
  941.     
  942.     glFeedbackBuffer(buffer_size,GL_2D,feedback_buffer);
  943.     glRenderMode(GL_FEEDBACK);
  944.     glBegin(GL_LINE_LOOP);
  945.     if(dim==3)
  946.     {
  947.         for(i=0;i<cnt;i++)
  948.             glVertex3fv(pts+i*stride);
  949.     }
  950.     else
  951.     {
  952.         for(i=0;i<cnt;i++)
  953.             glVertex4fv(pts+i*stride);
  954.     }
  955.     glEnd();
  956.     visible_cnt=glRenderMode(GL_RENDER);
  957.  
  958.     revert_sampling_and_culling(nobj);
  959.     return (GLboolean)(visible_cnt==0);
  960. }*/
  961.  
  962.